淘宝的推荐系统
- 题目链接：https://nanti.jisuanke.com/t/26984
- 参考的代码链接：https://blog.csdn.net/m0_38013346/article/details/80305150
简单的dp
- 对于每次的价格，与之前所有的价格以及对应的最大推荐数量进行比较，进行更新。复杂度为$O(N^2)$。这种方法会超时。
代码
#include <cstdlib> #include <string> #include <iostream> #include <fstream> #include <vector> #include <sstream> #include <unordered_map> #include <algorithm> #include <map> #include <set> #include <unordered_set> #include <stdio.h> #include <string.h> #include <numeric> using namespace std; typedef long long ll; int main() { int T = 0; scanf("%d", &T); for (int t = 0; t < T; t++) { int n = 0, d = 0; scanf("%d %d", &n, &d); vector<int> nums(n, 0); for (int i = 0; i < n; i++) scanf("%d", &nums[i]); vector<int> result( n, 0 ); result[0] = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (abs(nums[i] - nums[j]) <= d) result[i] = max(result[i], result[j] + 1); } } printf( "%d\n", result.back()); } return 0; }
结合每次价格的上下限进行处理
- 再添加一个数组用于维护在到达某件商品时，以价格为i结束，所推荐的最大个数。可以降低时间复杂度至$O(100000N)$。
代码
#include <cstdlib> #include <string> #include <iostream> #include <fstream> #include <vector> #include <sstream> #include <unordered_map> #include <algorithm> #include <map> #include <set> #include <unordered_set> #include <stdio.h> #include <string.h> #include <numeric> using namespace std; typedef long long ll; int main() { int T = 0; scanf("%d", &T); for (int t = 0; t < T; t++) { int n = 0, d = 0; scanf("%d %d", &n, &d); vector<int> nums(n, 0); vector<int> MaxN(1e5 + 5, 0); // MaxN[i]在某一时刻，以价格为i结束，所推荐的最大个数 for (int i = 0; i < n; i++) scanf("%d", &nums[i]); vector<int> dp( n, 0 ); // dp[i] 以第i件商品最后的推荐时的最大个数 for (int i = 0; i < n; i++) { int temp = 0; for (int j = max(nums[i] - d, 0); j <= min(nums[i] + d, 100000); j++) temp = max( temp, MaxN[j] ); // 之后引进的价格变量会对之前的结果进行更新 dp[i] = temp + 1; MaxN[nums[i]] = dp[i]; } int result = 0; for (int i = 0; i < n; i++) result = max( result, dp[i] ); printf( "%d\n", result); } return 0; }
阿里巴巴的手机代理商（简单）
思路
- 直接解析字符串即可，因为C++中没有现成的字符串分割程序，因此需要自己编写
- 提升运行速度的2个办法
- 分割字符串时，使用const引用的方法传入字符串
- 使用hashmap存储字符串信息，保证操作的时候时间复杂度为$O(1)$。
代码
#include <cstdlib> #include <string> #include <iostream> #include <fstream> #include <vector> #include <sstream> #include <unordered_map> #include <algorithm> #include <map> #include <set> #include <unordered_set> #include <stdio.h> #include <string.h> #include <numeric> using namespace std; typedef long long ll; //字符串分割函数 std::vector<std::string> split(const std::string &str, const std::string &pattern) { std::string::size_type pos; std::vector<std::string> result; int size = str.size(); for (int i = 0; i<size; i++) { pos = str.find(pattern, i); if (pos != -1 ) { result.push_back(str.substr(i, pos - i)); i = pos + pattern.size() - 1; } else { result.push_back(str.substr(i)); break; } } return result; } int main() { int T = 0; scanf("%d", &T); for (int t = 0; t < T; t++) { int n = 0; unordered_map<string, int> maps; scanf("%d\n", &n); // 加1个换行符号，否则之后读入字符串时，第一个读入的字符串是换行符 char chs[10000]; for (int i = 0; i < n; i++) { gets( chs ); string str(chs); vector<string> sstrs = split( str, " " ); if (sstrs[0] == "insert") { maps[sstrs[1]] += stoi( sstrs.back() ); } else if (sstrs[0] == "delete") { if (maps.find(sstrs[1]) == maps.end()) { printf("Empty\n"); } else { maps.erase(sstrs[1]); } } else if (sstrs[0] == "query") { int ret = 0; for (auto it = maps.begin(); it != maps.end(); it++) { if (it->first.size() >= sstrs[1].size() && it->first.substr(it->first.size() - sstrs[1].size()) == sstrs.back()) ret += it->second; } printf("%d\n", ret); } } } return 0; }